package com.cty.questions;


import java.util.HashSet;

import java.util.Set;

/*
 *给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *要用hashSet因为hashSet不能存入相同的两个元素，这样判断出的对象ListNode就是同一个
 * */
public class IntersectingLinkedLists {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode temp = headA;
        Set<ListNode> set = new HashSet<>();
        while (temp != null) {
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (set.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    //双指针法(两个指针走的距离是相等的，若碰到同一个结点哪一点是相交结点的第一个，
    // 如果两个链表不相交，那当他们距离相等时，也同时为空，也是相等的，这是返回的就是null)
    public ListNode getIntersectionNode02(ListNode headA, ListNode headB) {
        if (headA ==null || headB == null) {
            return null;
        }
        ListNode p = headA;
        ListNode q = headB;
        while (p != q) {
            p = p == null ? headB : p.next;
            q = q == null ? headA : q.next;
        }
        return p;
    }
}
